package com.mgq.algorithm.array;

import java.util.Arrays;

/**
 * 小和问题
 * 1,3,4,2,5
 * <p>
 * <p>
 * 1 3 4   2 5
 * <p>
 * 1 3    2 5
 * res=1
 */
public class SmallSum {

    public static void main(String[] args) {
        int[] array = {1, 3, 4, 2, 5};
        int process = process(array, 0, array.length - 1);
        System.out.println(process);
    }

    /**
     * 既要排好序,又要求小和
     *
     * @param array
     * @param L
     * @param R
     * @return
     */
    public static int process(int[] array, int L, int R) {
        if (L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return
                // 左侧排好序求小和
                process(array, L, mid)
                        // 右侧排好序求小和
                + process(array, mid + 1, R)
                        //合并再求小和
                + merge(array, L, mid, R);
    }

    private static int merge(int[] array, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int res = 0;
        int p1 = L;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= R) {
            //求最小和
            res += array[p1] < array[p2] ? (R - p2 + 1) * array[p1] : 0;
            //排序
            help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
        }
        //出了循环,表示要么p1越界,要么p2越界,把剩下的元素复制到help[]
        while (p1 <= mid) {
            help[i++] = array[p1++];
        }
        while (p2 <= R) {
            help[i++] = array[p2++];
        }
        // 归并排序的时候,首先保证部分有序,最后merge一次  help已经排好序了,复制数组
        for (int j = 0; j < help.length; j++) {
            array[L + j] = help[j];
        }
        System.out.println(Arrays.toString(array));
        System.out.println(res);
        return res;
    }
}
